11285. Найдите XOR на отрезке

 

Задан массив a. Вычислите значение XOR (побитовое исключающее или) на отрезке.

 

Вход. Первая строка содержит количество элементов массива n (1 ≤ n ≤ 106).

Вторая строка содержит n целых чисел ai​ (0 ≤ ai ​≤ 109) – элементы массива a.

Третья строка содержит количество запросов q (1 ≤ q ≤ 106) поиска XOR на отрезке.

Каждая из следующих q строк содержит по два целых числа li и ri (1 ≤ li ​≤ ri ≤ n) – границы отрезка массива, на котором нужно найти XOR.

 

Выход. Для каждого запроса в отдельной строке выведите XOR элементов на соответствующем отрезке массива (включая границы).

 

Пример входа

Пример выхода

5

1 2 3 4 5

5

1 5

2 4

3 5

1 3

3 4

1

5

2

0

7

 

 

РЕШЕНИЕ

частичные суммы

 

Анализ алгоритма

Рссмотрим частичные суммы массива а (по отношению к операции XOR):

s1 = a1;

s2 = a1 XOR a2;

s3 = a1 XOR a2 XOR a3;

. . .

sn = a1 XOR a2 XOR a3 XOR . . . XOR an;

Вычислить значения s1, s2, …, sn можно в линейном массиве s за время O(n).

Далее заметим, что

Sl,r = al XOR al+1 XOR . . . XOR ar-1 XOR ar = sr XOR sl-1

Таким образом ответить на запрос Sl,r можно за константное время.

 

Пример

Вычислим массив частичных сумм для заданного примера.

Ответами на запросы будут:

S1,5 = s5 XOR s0 = 1 XOR 0 = 1;

S2,4 = s4 XOR s1 = 4 XOR 1 = 5;

S3,5 = s5 XOR s2 = 1 XOR 3 = 2;

S1,3 = s3 XOR s0 = 0 XOR 0 = 0;

S3,4 = s4 XOR s2 = 4 XOR 3 = 7;

 

Реализация алгоритма

Объявим массив s для хранения частичных сумм.

 

#define MAX 1000001

int s[MAX];

 

Читаем размер массива n.

 

scanf("%d", &n);

 

Читаем входной массив и вычисляем его частичные суммы:

si = a1 XOR a2 XOR a3 XOR . . . XOR ai = si-1 XOR ai

 

s[0] = 0;

for (i = 1; i <= n; i++)

{

  scanf("%d", &x);

  s[i] = s[i - 1] ^ x;

}

 

Обрабатываем q запросов.

 

scanf("%d", &q);

for (i = 0; i < q; i++)

{

  scanf("%d %d", &l, &r);

 

Для каждого запроса [l, r] выводим ответ sl-1 XOR sr.

 

  printf("%d\n", s[l - 1] ^ s[r]);

}

 

Python реализация

Читаем входные данные.

 

n = int(input())

a = list(map(int, input().split()))

 

Объявим список s для хранения частичных сумм.

 

s = [0] * (n + 1)

 

Вычисляем частичные суммы списка a.

 

for i in range(n):

  s[i + 1] = s[i] ^ a[i]

 

Обрабатываем q запросов.

 

q = int(input())

for _ in range(q):

  l, r = map(int, input().split())

 

Для каждого запроса [l, r] выводим ответ sl-1 XOR sr.

 

  print(s[l - 1] ^ s[r])